|
In numerical analysis, pairwise summation, also called cascade summation, is a technique to sum a sequence of finite-precision floating-point numbers that substantially reduces the accumulated round-off error compared to naively accumulating the sum in sequence. Although there are other techniques such as Kahan summation that typically have even smaller round-off errors, pairwise summation is nearly as good (differing only by a logarithmic factor) while having much lower computational cost—it can be implemented so as to have nearly the same cost (and exactly the same number of arithmetic operations) as naive summation. In particular, pairwise summation of a sequence of ''n'' numbers ''xn'' works by recursively breaking the sequence into two halves, summing each half, and adding the two sums: a divide and conquer algorithm. Its worst-case roundoff errors grow asymptotically as at most ''O''(ε log ''n''), where ε is the machine precision (assuming a fixed condition number, as discussed below).〔 In comparison, the naive technique of accumulating the sum in sequence (adding each ''xi'' one at a time for ''i'' = 1, ..., ''n'') has roundoff errors that grow at worst as ''O''(ε''n'').〔 Kahan summation has a worst-case error of roughly ''O''(ε), independent of ''n'', but requires several times more arithmetic operations.〔 If the roundoff errors are random, and in particular have random signs, then they form a random walk and the error growth is reduced to an average of for pairwise summation.〔Manfred Tasche and Hansmartin Zeuner ''Handbook of Analytic-Computational Methods in Applied Mathematics'' Boca Raton, FL: CRC Press, 2000).〕 A very similar recursive structure of summation is found in many fast Fourier transform (FFT) algorithms, and is responsible for the same slow roundoff accumulation of those FFTs.〔〔S. G. Johnson and M. Frigo, "(Implementing FFTs in practice ), in ''(Fast Fourier Transforms )'', edited by C. Sidney Burrus (2008).〕 Pairwise summation is the default summation algorithm in NumPy〔(ENH: implement pairwise summation ), github.com/numpy/numpy pull request #3685 (September 2013).〕 and the Julia technical-computing language,〔(RFC: use pairwise summation for sum, cumsum, and cumprod ), github.com/JuliaLang/julia pull request #4039 (August 2013).〕 where in both cases it was found to have comparable speed to naive summation (thanks to the use of a large base case). ==The algorithm== In pseudocode, the pairwise summation algorithm for an array ''x'' of length ''n'' > 0 can be written: ''s'' = pairwise(''x''()) if ''n'' ≤ ''N'' ''base case: naive summation for a sufficiently small array'' ''s'' = ''x''() for ''i'' = 2 to ''n'' ''s'' = ''s'' + ''x''() else ''divide and conquer: recursively sum two halves of the array'' ''m'' = floor(''n'' / 2) ''s'' = pairwise(''x''()) + pairwise(''x''()) endif For some sufficiently small ''N'', this algorithm switches to a naive loop-based summation as a base case, whose error bound is O(Nε). The entire sum has a worst-case error that grows asymptotically as ''O''(ε log ''n'') for large ''n'', for a given condition number (see below). In an algorithm of this sort (as for divide and conquer algorithms in general〔Radu Rugina and Martin Rinard, "(Recursion unrolling for divide and conquer programs )," in ''Languages and Compilers for Parallel Computing'', chapter 3, pp. 34–48. ''Lecture Notes in Computer Science'' vol. 2017 (Berlin: Springer, 2001).〕), it is desirable to use a larger base case in order to amortize the overhead of the recursion. If ''N'' = 1, then there is roughly one recursive subroutine call for every input, but more generally there is one recursive call for (roughly) every ''N''/2 inputs if the recursion stops at exactly ''n'' = ''N''. By making ''N'' sufficiently large, the overhead of recursion can be made negligible (precisely this technique of a large base case for recursive summation is employed by high-performance FFT implementations〔). Regardless of ''N'', exactly ''n''−1 additions are performed in total, the same as for naive summation, so if the recursion overhead is made negligible then pairwise summation has essentially the same computational cost as for naive summation. A variation on this idea is to break the sum into ''b'' blocks at each recursive stage, summing each block recursively, and then summing the results, which was dubbed a "superblock" algorithm by its proposers.〔Anthony M. Castaldo, R. Clint Whaley, and Anthony T. Chronopoulos, "Reducing floating-point error in dot product using the superblock family of algorithms," ''SIAM J. Sci. Comput.'', vol. 32, pp. 1156–1174 (2008).〕 The above pairwise algorithm corresponds to ''b'' = 2 for every stage except for the last stage which is ''b'' = ''N''. 抄文引用元・出典: フリー百科事典『 ウィキペディア（Wikipedia）』 ■ウィキペディアで「Pairwise summation」の詳細全文を読む スポンサード リンク
|